from math import sqrt
def numSquares(n):
    if n <= 0:
        return 0
    legal_nums = [e**2 for e in range(1, int(sqrt(n)) + 1)]
    layers = 0
    current_queue = {n}
    while current_queue:
        layers+=1
        next_queue = set()
        for elem in current_queue:
            for legal_num in legal_nums:
                if elem == legal_num:
                    return layers
                elif elem<legal_num:
                    break
                else:
                    next_queue.add(elem-legal_num)
        current_queue = next_queue
    return layers

def main():
    n = 12
    # print(numSquares(0))
    print(numSquares(7168))
    print(numSquares(n))
if __name__ == "__main__":
    main()